#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-11 10:25 上午
# @Author  : yangdy
# @File    : 2020-08-11.130.被围绕的区域
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        n, m = len(board), len(board[0])
        ss = [[-1 for i in range(m)] for j in range(n)]
        sp = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        rs, lr = [], 0

        def dfs(x, y):
            if ss[x][y] != -1:
                return
            ss[x][y] = lr
            for spi in sp:
                xx, yy = x+spi[0], y+spi[1]
                if 0 <= xx < n and 0 <= yy < m:
                    if board[xx][yy] != 'O':
                        continue
                    dfs(xx, yy)
                else:
                    rs[lr] = 1

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O' and ss[i][j] == -1:
                    rs.append(0)
                    dfs(i, j)
                    lr += 1
        for i in range(n):
            for j in range(m):
                if ss[i][j] != -1 and rs[ss[i][j]] == 0:
                    board[i][j] = 'X'


questions = [
    ([['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'],
      ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']],),
]

work(questions, lambda q: Solution().solve(q[0]))
